﻿#region

using Common.Utilities;

#endregion

namespace AdvancedTraining.Lesson47;

// 需要证明：
// 一个集合中，假设整体的累加和为K，
// 不管该集合用了什么样的0集合划分方案，当一个新的数到来时：
// 1) 如果该数是-K，那么任何0集合的划分方案中，因为新数字的加入，0集合的数量都会+1
// 2) 如果该数不是-K，那么任何0集合的划分方案中，0集合的数量都会不变
public class OptimalAccountBalancing //leetcode_0465
{
    // 用位信息替代集合结构的暴力尝试
    private static int MinTransfers1(int[][] transactions)
    {
        // 不管转账有几笔，最终每个人收到的钱，如果是0，不进入debt数组
        // 只有最终收到的钱，不等于0的人，进入debt数组
        // 收到的钱，4，说明该给出去！
        // 收到的钱，-4，说明该要回来！
        // debt数组的累加和，必为0！
        var debt = debts(transactions);
        var n = debt.Length;
        return n - Process1(debt, (1 << n) - 1, 0, n);
    }

    // set -> int -> 不使用值 -> 只使用状态！
    // 001110 0号人，不在集合里；1、2、3号人在集合里，4、5号人不在集合里！
    // sum -> set这个集合累加和是多少？sum被set决定的！
    // debt数组，收到的钱的数组(固定)
    // N, debt的长度(固定)
    // 返回值含义 : set这个集合中，最多能划分出多少个小集合累加和是0，返回累加和是0的小集合最多的数量
    private static int Process1(int[] debt, int set, int sum, int N)
    {
        // set中只有一个人的时候！
        // debt中，没有0的，所以每个人一定都需要转账！
        if ((set & (set - 1)) == 0) return 0;
        var max = 0;
        // 尝试，每一个人都最后考虑
        // 0,如果最后考虑
        // 1,如果最后考虑
        // 2,如果最后考虑
        // ....
        // n-1，最后考虑
        // 011001
        // 0（在）
        // 1（不能考虑！因为不在集合里！）
        for (var i = 0; i < N; i++)
        {
            var value = debt[i];
            if ((set & (1 << i)) != 0)
                // i号人真的在集合里，才能考虑！
                // 011001
                // 3号人在
                // 3号人之前，010001（考虑0号人和4号人剩下的情况）
                // process ( set ^ (1 << i) , sum - value )
                max = Math.Max(max, Process1(debt, set ^ (1 << i), sum - value, N));
        }

        return sum == 0 ? max + 1 : max;
    }

    // 上面的尝试过程 + 记忆化搜索
    // 最优解
    private static int MinTransfers2(int[][] transactions)
    {
        var debt = debts(transactions);
        var n = debt.Length;
        var sum = 0;
        foreach (var num in debt) sum += num;
        var dp = new int[1 << n];
        Array.Fill(dp, -1);
        return n - Process2(debt, (1 << n) - 1, sum, n, dp);
    }

    private static int Process2(int[] debt, int set, int sum, int n, int[] dp)
    {
        if (dp[set] != -1) return dp[set];
        var ans = 0;
        if ((set & (set - 1)) != 0)
        {
            var max = 0;
            for (var i = 0; i < n; i++)
            {
                var value = debt[i];
                if ((set & (1 << i)) != 0) max = Math.Max(max, Process2(debt, set ^ (1 << i), sum - value, n, dp));
            }

            ans = sum == 0 ? max + 1 : max;
        }

        dp[set] = ans;
        return ans;
    }

    private static int[] debts(int[][] transactions)
    {
        var map = new Dictionary<int, int>();
        foreach (var tran in transactions)
        {
            map[tran[0]] = map.GetValueOrDefault(tran[0], 0) + tran[2];
            map[tran[1]] = map.GetValueOrDefault(tran[1], 0) - tran[2];
        }

        var n = 0;
        foreach (var value in map.Values)
            if (value != 0)
                n++;
        var debt = new int[n];
        var index = 0;
        foreach (var value in map.Values)
            if (value != 0)
                debt[index++] = value;
        return debt;
    }

    // 为了测试
    private static int[][] randomTrans(int s, int n, int m)
    {
        var trans = new int[s][];
        for (var i = 0; i < trans.Length; i++)
            trans[i] = new[]
            {
                (int)(Utility.getRandomDouble * n),
                (int)(Utility.getRandomDouble * n),
                (int)(Utility.getRandomDouble * m) + 1
            };

        return trans;
    }

    // 为了测试
    public static void Run()
    {
        var s = 8;
        var n = 8;
        var m = 10;
        var testTime = 10000;
        Console.WriteLine("测试开始");
        for (var i = 0; i < testTime; i++)
        {
            var trans = randomTrans(s, n, m);
            var ans1 = MinTransfers1(trans);
            var ans2 = MinTransfers2(trans);
            if (ans1 != ans2)
            {
                Console.WriteLine("出错啦！");
                Console.WriteLine(ans1);
                Console.WriteLine(ans2);
                break;
            }
        }

        Console.WriteLine("测试结束");
    }
}